
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "comm.h"


struct unit
{
    int value;
    int backup[9];
};


static unsigned char input[9][9] = {
    {2, 0, 0, 6, 0, 0, 0, 5, 0},
    {0, 8, 0, 9, 0, 2, 0, 0, 0},
    {0, 0, 0, 0, 4, 0, 6, 0, 0},
    {0, 0, 0, 4, 0, 9, 0, 0, 6},
    {5, 0, 0, 0, 0, 0, 0, 9, 0},
    {0, 9, 0, 2, 0, 0, 1, 4, 0},
    {0, 0, 1, 0, 0, 0, 0, 0, 3},
    {0, 4, 0, 3, 1, 0, 0, 0, 0},
    {0, 2, 0, 0, 0, 0, 0, 0, 8}
};

void print_map(unsigned char input[9][9])
{
    int i, j;

    for (i = 0; i < 9; ++i) {
        if (i % 3 == 0)
            printf("#===#===#===#===#===#===#===#===#===\n");
        else
            printf(" --- --- --- --- --- --- --- --- ---\n");

        for (j = 0; j < 9; ++j) {
            printf("%s %d ", j % 3 == 0 ? "/" : "|", input[i][j]);
        }
        printf("/\n");
    }
    printf("#===#===#===#===#===#===#===#===#===\n");
}

void transfer2sudoku(unsigned char input[9][9], struct unit output[9][9])
{
    int i, j;

    memset(output, 0x0, sizeof(struct unit) * 9 * 9);

    for (i = 0; i < 9; ++i) {
        for (j = 0; j < 9; ++j) {
            output[i][j].value = input[i][j];
        }
    }
}

static void sort(int *buff, int size)
{
    if (size <= 1) {
        return ;
    }

    int i, j, key;

    for (j = 1; j < size; ++j) {
        key = buff[j];
        i = j - 1;
        // tc_log("key = buff[%d] = 0x%x buff[%d] 0x%x", j, key, i, buff[i]);

        if (key != 0) {
            while ((i >= 0 && buff[i] > key) || buff[i] == 0) {
                buff[i + 1] = buff[i];
                // tc_log("buff[%d] 0x%x", i + 1, buff[i + 1]);
                i--;
            }

            // tc_log("i %d j %d", i, j);
            buff[i + 1] = key;
        }

        // hexdump_int(buff, size, "buff during sort");
    }
}

void print_sudoku(struct unit sudoku[9][9])
{
    int i, j, n, m, g, h;

    for (i = 0; i < 9; ++i) {
        for (j = 0; j < 9; ++j) {
            sort(sudoku[i][j].backup, 9);
        }
    }

    for (i = 0; i < 9; ++i) {
        if (i % 3 == 0)
            printf("#=====#=====#=====#=====#=====#=====#=====#=====#=====\n");
        else
            printf(" ----- ----- ----- ----- ----- ----- ----- ----- -----\n");

        // sub-row
        for (h = 0; h < 3; ++h) {

            for (j = 0; j < 9; ++j) {

                if (sudoku[i][j].value != 0) {
                    if (h == 0)
                        printf("%s %d   ", j % 3 == 0 ? "/" : "|", sudoku[i][j].value);
                    else
                        printf("%s     ", j % 3 == 0 ? "/" : "|");
                }
                else {
                    printf("%s ", j % 3 == 0 ? "/" : "|");

                    for (g = 0; g < 3; ++g) {
                        if (sudoku[i][j].backup[h*3 + g] == 0)
                            printf(" ");
                        else
                            printf("%d", sudoku[i][j].backup[h*3 + g]);
                    }

                    printf(" ");
                }
            }
            printf("/\n");
        }
    }
    printf("#=====#=====#=====#=====#=====#=====#=====#=====#=====\n");
}

static int insert(int *buf, int size, int val)
{
    int i;

    for (i = 0; i < size; ++i) {
        if (buf[i] == 0) 
            buf[i] = val;
    }
}

int find_blk_missing_num(struct unit sudoku[9][9], int blk, unsigned char miss[9])
{
    int i, j, s_row, s_column, count = 0;

    s_row = blk / 3 * 3;
    s_column = blk % 3 * 3;

    for (i = s_row; i < (s_row +3); ++i) {
        for (j = s_column; j < (s_column + 3); ++j) {
            if (sudoku[i][j].value != 0) {
                miss[sudoku[i][j].value - 1] = 0;
            }
            else {
                count++;
            }
        }
    }

    return count;
}

int check_row_column(unsigned char input[9][9], int p_row, int p_column, int num)
{
    int row, colu;

    // check row
    for (colu = 0; colu < 9; ++colu) {
        if (colu == p_column)
            continue;

        if (input[p_row][colu] == num) {
            // tc_log("find [%d][%d] same with %d", p_row, colu, num);
            return -1;
        }
    }

    // check column
    for (row = 0; row < 9; ++row) {
        if (row == p_row)
            continue;

        if (input[row][p_column] == num) {
            // tc_log("find [%d][%d] same with %d", row, p_column, num);
            return -1;
        }
    }

    // tc_log("num %d at [%d][%d] is valid", num, p_row, p_column);
    return 0;
}

int fill_blk_way1(struct unit sudoku[9][9], int blk, unsigned char miss[9])
{
    int s_row, s_column, i, j, n, valid, valid_num, update;

    s_row = blk / 3 * 3;
    s_column = blk % 3 * 3;

    update = 0;

    for (i = s_row; i < (s_row +3); ++i) {
        for (j = s_column; j < (s_column + 3); ++j) {
            if (sudoku[i][j].value != 0)
                continue;

            valid = 0;
            memset(sudoku[i][j].backup, 0x0, sizeof(sudoku[i][j].backup));

            for (n = 0; n < 9; ++n) {
                if (miss[n] == 0)
                    continue;

                // check this miss num at this possition
                // tc_log("check miss number %d at [%d][%d]", miss[n], i, j);

                if (check_row_column(sudoku, i, j, miss[n]) >= 0){
                    valid++;
                    valid_num = miss[n];
                    insert(sudoku[i][j].backup, sizeof(sudoku[i][j].backup), miss[n]);
                }
            }

            // tc_log("[%d][%d] valid %d", i, j, valid);

            if (valid == 1) {
                sudoku[i][j].value = valid_num;
                memset(sudoku[i][j].backup, 0x0, sizeof(sudoku[i][j].backup));
                update++;
            }
        }
    }

    return update;
}

int fill_blk_way2(struct unit sudoku[9][9], int blk, unsigned char miss[9])
{
    int s_row, s_column, i, j, n, valid, valid_row, valid_colu, update;

    s_row = blk / 3 * 3;
    s_column = blk % 3 * 3;

    update = 0;

    for (n = 0; n < 9; ++n) {
        if (miss[n] == 0)
            continue;

        valid = 0;

        for (i = s_row; i < (s_row +3); ++i) {
            for (j = s_column; j < (s_column + 3); ++j) {
                if (sudoku[i][j].value != 0)
                    continue;

                // check this miss num at this possition
                // tc_log("check miss number %d at [%d][%d]", miss[n], i, j);

                if (check_row_column(sudoku, i, j, miss[n]) >= 0){
                    valid++;
                    valid_row = i;
                    valid_colu = j;
                }
            }
        }

        // tc_log("[%d][%d] valid %d", i, j, valid);

        if (valid == 1) {
            sudoku[valid_row][valid_colu].value = miss[n];
            update++;
        }
    }

    return update;
}

int main(int argc, char const *argv[])
{
    int round, i, j, miss_cnt, update;
    unsigned char miss_num[9];
    struct unit sudoku[9][9];

    tc_log("********************");
    tc_log("new start @ %s %s", __DATE__, __TIME__);
    tc_log("********************");

    print_map(input);
    transfer2sudoku(input, sudoku);
    print_sudoku(sudoku);

#if 1
    round = 0;
    while (++round) {
        tc_log("round %d", round);

        update = 0;

        // try way 1
        for (i = 0; i < 9; ++i) {

            for (j = 0; j < 9; ++j){
                miss_num[j] = j + 1;
            }
            miss_cnt = find_blk_missing_num(sudoku, i, miss_num);
            // tc_log("miss_cnt %d", miss_cnt);
            // hexdump(miss_num, sizeof(miss_num), "miss_num");

            update += fill_blk_way1(input, i, miss_num);
        }

        // try way 2
        for (i = 0; i < 9; ++i) {

            for (j = 0; j < 9; ++j){
                miss_num[j] = j + 1;
            }
            miss_cnt = find_blk_missing_num(sudoku, i, miss_num);
            // tc_log("miss_cnt %d", miss_cnt);
            // hexdump(miss_num, sizeof(miss_num), "miss_num");

            update += fill_blk_way2(input, i, miss_num);
        }

        if (update == 0) {
            tc_log("nothing update failed at round %d", round);
            break;
        }

        for (i = 0; i < 9; ++i) {
            if (find_blk_missing_num(sudoku, i, miss_num) > 0)
                break;
        }

        if (i == 9) {
            tc_log("complete at round %d", round);
            break;
        }
    }

    print_sudoku(sudoku);
#endif

    tc_log("exit");
    return 0;
}

